import java.util.ArrayList;
import java.util.List;
public class Solution {
    public List<String> generateParenthesis(int n) {

        List<String> list=new ArrayList<>();
        if(n==0){
            return list;
        }
        dfs("",n,n,list);

        return list;
    }

    private void dfs(String ans, int left, int right, List<String> list){
        //递归出口
        //左右括号都用完时退出
        if(left == 0 && right == 0){
            list.add(ans);
            return;
        }
        //如果左括号可用的比右括号可用的多也退出
        //必须先用左括号
        //否则不配对
        if(left > right){
            return ;
        }
        //左右括号如果没用完一直递归拼接
        if(left > 0){
            dfs(ans+"(",left-1,right,list);
        }
        if(right > 0){
            dfs(ans+")",left,right-1,list);
        }

    }
}